perm filename PAGE26[00,BGB] blob
sn#046254 filedate 1973-06-06 generic text, type T, neo UTF8
~F82. CONTOURING.
Contouring, converts the bit arrays HSEG and VSEG into
vectors and polygons. The contouring itself, is done by a single
subroutine named MKPGON, make polygon. When MKPGON is called, it
looks for the upper most left non-zero bit in the VSEG array. If the
VSEG array is empty, MKPGON returns a NIL. However, when the bit is
found, MKPGON traces and erases the polygonal outline to which that
bit belongs and returns a polygon node with a ring of vectors.
To belabor the details (for the sake of later complexities);
the MKGON trace can go in four directions: north and south along
vertical columns of bits in the VSEG array, or east and west along
horizontal rows of the HSEG array. The trace starts by heading south
until it hits a turn; when heading south MKPGON must check for first
a turn to the east (indicated by a bit in HSEG); next for no turn
(continue south); and last for a turn to the west. When a turn is
encountered MKPGON creates a vector node representing the run of
bits between the previous turn and the present turn. The trace
always ends heading west bound. The outline so traced can be either
the edge of a blob or a hole, the two cases are distinguished by
looking at the VIC-polygon's uppermost left pixel in the PAC bit
array.
There are two complexities: contrast accumulation and
dekinking. The contrast of a vector is defined as (QUOTIENT
(DIFFERENCE (Sum of pixel values on one side of the vector)(Sum of
pixel values on the other side of the vector)) (length of the vector
in pixels)). Since vectors are always either horizontal or vertical
and are construed as being on the cracks between pixels; the
specified summations refer to the pixels immediately to either side
of the vector. Notice that this definition of constrast will always
give a positive constrast for vectors of a blob and negative
contrast for the vectors of a hole.
The terms "jaggies", "kinks" and "sawtooth" all are used to
express what seems to be wrong about the lowermost left polygon on
page 25. The problem involves doing something to a rectilinear
quantized set of segments, to make its linear nature more evident.
The CRE jaggies solution (in the subroutine MKPGON) merely positions
the turning locus diagonally off its grid point alittle in the
direction (northeast, northwest, southwest or southeast) that
bisects the turn's right angle. The distance of dekink vernier
positioning is always less than half a pixel; but greater for
brighter cuts and less for the darker cuts; in order to preserve the
nesting of contours. The saw toothed and the dekinked versions of a
polygon have the same number of vectors. I am very fond of this
dekinking algorithm because of its incredible efficiency; given that
you have a north, south, east, west polygon trace routine (which
handles image coordinates packed row, column into one accumulator
word); then dekinking requires only one more ADD instruction
execution per vector ! ~I1973,800;F8- 26 -